package com.leetcode.problems_06;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 0020：有效的括号
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']的字符串 s ，判断字符串是否有效。
 *
 * 有效字符串需满足：
 *      左括号必须用相同类型的右括号闭合。
 *      左括号必须以正确的顺序闭合。
 *
 * 使用栈
 *
 * @Author: WuPeng
 * @Date: 2021/5/17 10:56 下午
 */
public class ValidBrackets {

    public static boolean isValid(String brackets){

        Deque<Character> deque = new LinkedList<>();

        for (int i=0; i<brackets.length(); i++){
            char c = brackets.charAt(i);
            if (c == '(')
                deque.push(')');
            else if (c == '[')
                deque.push(']');
            else if (c == '{')
                deque.push('}');
            else if (deque.isEmpty() || deque.peek() != c)
                return false;
            else
                deque.pop();
        }
        return deque.isEmpty();
    }

    public static void main(String[] args) {
//        String brackets = "(([{{}}]))";
        String brackets = "(([{{}}])";

        System.out.println(isValid(brackets));

    }
}
